package Lintcode;

import java.util.Scanner;

/**
 * Question: https://www.lintcode.com/zh-cn/problem/merge-two-sorted-arrays/
 * Solution:
 * Time: 2018/4/30
 * Coder: Ksxy 
**/
public class Merge_two_sorted_arrays {

    static Scanner scanner = null;
    static {
        scanner = new Scanner(System.in);
    }

    public static void main(String[] args) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int[] A = new int[a], B = new int[b];
        for(int i=0; i < a; i++) A[i] = scanner.nextInt();
        for(int i=0; i < b; i++) B[i] = scanner.nextInt();

        int[] reuslt = mergeSortedArray(A, B);
        for (int t: reuslt) {
            System.out.print(t + " ");
        }
    }

    public static int[] mergeSortedArray(int[] A, int[] B){
        int[] result = new int[A.length + B.length];
        int aPointer =0 ,bPointer = 0, rPointer = 0;
        while (aPointer < A.length && bPointer < B.length){
            if(A[aPointer] < B[bPointer]){
                result[rPointer++] = A[aPointer++];
            }else {
                result[rPointer++] = B[bPointer++];
            }
        }
        while (aPointer < A.length){
            result[rPointer++] = A[aPointer++];
        }
        while (bPointer < B.length){
            result[rPointer++] = B[bPointer++];
        }
        return result;
    }
}
